#include <vector>
#include <map>

using namespace std;

class Solution {
public:
    int findTargetSumWays(const vector<int>& nums, int target)
    {
        vector<map<int, int>> dp;
        int ret = 0;
        dp.push_back({ {nums[0],1},{-nums[0],1} });
        for (int i = 1; i < nums.size(); i++)
        {
            map<int, int> tmp;
            for (auto e : dp[i - 1])
            {
                tmp[e.first - nums[i]] += e.second;
                tmp[e.first + nums[i]] += e.second;
            }
            dp.push_back(move(tmp)), tmp.clear();
        }
        return dp[nums.size() - 1][target];
    }
};

int main()
{
    Solution().findTargetSumWays({ 0,0,0,0,0,0,0,0,1 },1);
	return 0;
}
